package algorithm.dynamic_planning.leetcode;

/**
 * @author yuisama
 * @date 2022年12月11日 19:18
 * @description LCS变种问题，要让s1和s2变为一样，就是将s1和s2中cls以外的字符剔除即可
 */
public class Num583_MinDistance {
    public int minDistance(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();
        int lcs = longestCommonSubsequence(word1,word2);
        return m - lcs + n - lcs;
    }

    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length();
        int n = text2.length();
        // 定义：s1[0..i-1] 和 s2[0..j-1] 的 lcs 长度为 dp[i][j]
        // 目标：s1[0..m-1] 和 s2[0..n-1] 的 lcs 长度，即 dp[m][n]
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                // 数组索引和字符串长度差了一个单位偏移量，因此此处为i-1和j-1
                // i和j都从1开始计数
                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    dp[i][j] = 1 + dp[i - 1][j - 1];
                }else {
                    dp[i][j] = Math.max(dp[i - 1][j],dp[i][j - 1]);
                }
            }
        }
        return dp[m][n];
    }
}
